package com.wujunshen.algorithm.leetcode.dynamic.programming;

/**
 * dp(x,y)=dp(x-1,y)+dp(x,y-1)-dp(x-1,y-1)+mat(x-1,y-1)
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/8/11 16:59<br>
 */
public class 二维区域和检索矩阵不可变 {
    public static void main(String[] args){
        int[][] arrays=new int[][]{{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};

        NumMatrix numMatrix = new NumMatrix(arrays);
        // return 8
        int result= numMatrix.sumRegion(2, 1, 4, 3);
        System.out.println("result is:"+result);
        // return 11
        result= numMatrix.sumRegion(1, 1, 2, 2);
        System.out.println("result is:"+result);
        // return 12
        result= numMatrix.sumRegion(1, 2, 2, 4);
        System.out.println("result is:"+result);
    }
}

class NumMatrix {
    private final int[][] dp;

    public NumMatrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;

        dp = new int[row + 1][col + 1];

        for (int x = 0; x < row; x++) {
            for (int y = 0; y < col; y++) {
                dp[x + 1][y + 1] = dp[x][y + 1] + dp[x + 1][y] - dp[x][y] + matrix[x][y];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1];
    }
}
